package com.example.demo.arithmetic.algorithm.dynamic_programing;

/**
 * leetcode1143 最长公共子序列
 * 一个字符串的 子序列 是指这样一个新的字符串：
 * 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * <p>
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 */

/*
多一行一列 初始化为0 方便处理边界问题
         a    b   c   x   y   z
    0    0    0   0   0   0   0
a   0    1    1   1   1   1   1
b   0    1    2   2   2   2   2
x   0    1    2   2   3   3   3
y   0    1    2   2   3   4   4
z   0    1    2   2   3   4   5

递推公式
if(相同）{
    dp[i][j]=dp[i-1][j-1]+1
}else{
    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])
}

 */
public class LCSubsequence {

    /**
     * @param a a    b   c   x   y   z
     * @param b a    b   x   y   z
     * @return
     */
    public int longestCommonSubsequence(String a, String b) {
        int maxLength = 0;
        int[][] dp = new int[b.length() + 1][a.length() + 1];
        for (int i = 1; i < b.length() + 1; i++) {
            for (int j = 1; j < a.length() + 1; j++) {
                if (b.charAt(i - 1) == a.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }

                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        printDp(dp);
        return maxLength;
    }

    private static void printDp(int[][] arr) {
        for (int[] its : arr) {
            for (int anInt : its) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        //System.out.println(new LCSubsequence().longestCommonSubsequence("abcde", "ace"));
        System.out.println(new LCSubsequence().longestCommonSubsequence("abcxyz", "abxyz"));
    }
}
